As used in the following discussion, the terms “Huffman code,” “symbol,” and “coefficient” have the following meanings. A “Huffman code” is used herein to refer to a Variable-Length Code (VLC). A “symbol” is a unit of information coded with, e.g., Huffman coding. A “coefficient” is the final, typically numerical, value of interest that is related to the symbol. For example, decoding a JPEG (Joint Picture Expert Group) Huffman code provides a symbol with information as to the bits required to represent a coefficient and implicit information as to the sign of the coefficient. Based on an interpretation of the symbol, a few additional bits are read from a bit stream and then a coefficient can be reconstructed.
JPEG is a widely used image compression standard. JPEG compresses an image by splitting the raw data into components, dividing each component into eight-pixel by eight-pixel blocks, applying a Discrete Cosine transform (DCT) to each block, quantizing the block coefficients, run-length encoding the coefficients in zigzag order, and finally Huffman-encoding symbols related to the run-lengths and non-zero coefficients.
JPEG decompression reverses these steps to restore the original image (minus quantization errors). In a typical decompression, 30% of the time is spent decoding the Huffman coding, another 30% is spent on inverse DCTs, and the remainder of the time is spent parsing, moving data, performing color transforms, etc. Many common microprocessors and signal processors contain optimizations to speed DCT and inverse DCT operations, thus further reducing the impact of these operations.
In many cases where the image is decompressed for viewing on a display, the actual image size is much larger than the final display size. For example, the display may just contain 640×480 pixels, while the actual image size may be 2560×1920 pixels (taken by a 5 megapixel camera, for instance). In this case, a technique applied (not part of this disclosure) is to do a reduced IDCT (two pixel by two pixel IDCT in this case) instead of the full IDCT, reducing IDCT complexity in this example by roughly a factor of sixteen. All subsequent data moves and color transforms are done on the basis of this reduced block size, resulting in similar saving for those operations as well. Note that the Huffman decoding is done before the IDCT; hence it has to be done fully no matter what the final display resolution. It is not possible to skip the decoding of higher coefficients since it is impossible to know where the next block's symbols start, without decoding all of the coefficients in the current block.
In a case where the display size is smaller than the image size, since the IDCT and subsequent modules have been modified to skip some processing, the percentage of time spent in the Huffman module increases, as compared to the other modules. For example, for decoding using the two by two IDCT, 60–80% of the decompression time is spent in Huffman decoding. This is especially true for images with high quality, as is the case with digital cameras with high resolution. Hence it becomes an important issue to speed up the Huffman decoding.
As explained above, JPEG compression operates on eight-pixel by eight-pixel blocks. The DCT coefficients from each block are zigzag scanned into a one-dimensional array, and these are run-length encoded. The run and level are assigned a Huffman Variable Length Code as explained in Section F of the JPEG standard (CCITT Recommendation T.81). The Huffman table is indicated in the JPEG bit stream in a particular format. Huffman tables are specified in terms of a sixteen-element list giving the number of codes for each code length from one to sixteen. This is followed by a list of eight-bit symbol values, each of which is assigned a Huffman code. The symbol values are placed in the list in order of increasing code length. Code lengths greater than sixteen bits are not allowed, as explained in section C of the JPEG standard. Symbols have different meanings, depending on whether a coefficient is an AC or a DC value.
Each JPEG block has one DC coefficient, which is differentially coded. The remaining 63 (AC) coefficients are arranged linearly in zigzag scan order. Also, from the symbol itself only partial coefficient information is available; a certain number of following bits will have to be read from the bit stream in order to refine the coefficient and determine its sign. When a run of more than fifteen zeros occurs in the AC coefficients, this condition is coded with a special escape sequence. It is also possible to terminate a block with a special symbol called End of Block (EOB) when a run of zeros continues to the end of the block. These nuances complicate and slow the serial Huffman decoding procedure in JPEG.
It is possible to traverse a symbol tree bit-by-bit to perform Huffman decoding, but this requires a decision per bit decoded and is usually inefficient. Instead, it has been observed that most of the time the symbols have a length less than seven or eight bits. Hence it is common to have a lookup table for symbol-lookup. Given a length L, all Huffman codes of length L or less are decoded with a single table access. When a code has a length greater than L, additional decoding operations are needed. Also, since the retrieval of the actual coefficient involves many arithmetic operations, it is common to maintain a bit buffer (denoted hence forth as “bit—buffer”). All the lookup, indexing, and arithmetic operations are performed on this bit—buffer register. Normally this register is chosen to be the widest register in the processor. Also, for efficient input-output, it is typical to have a byte-buffer (typically a few kilobytes) that keeps a portion of the compressed stream in memory. When enough bit—buffer bits are not available for lookup of the next symbol, bytes are transferred from this byte-buffer to the bit—buffer. Every time this happens, the maximum possible number of bytes is transferred to minimize the number of such transfers.
A simple example will now be presented for decoding a single Huffman codeword using a standard lookup table technique. To keep the example brief, only three symbols (0, +1, −1) are used, and are assigned the respective codewords 1, 01, and 00, as shown in Table 1 below.
TABLE 1CodewordSymbol1001+100−1Using a look-ahead value of two bits, the next symbol can be decoded from the bit—buffer by extracting the next two bits and looking up a symbol from the following lookup table (Table 2):
TABLE 2Look-ahead ValueCode LengthSymbol002−1012+110101110The Code Length column in Table 2 tells the algorithm how many bit—buffer bits were consumed in looking up the next symbol. During decoding, the bit buffer is shifted by this many bits after a symbol lookup, and then the next symbol is looked up. This process is illustrated in Table 3 below, for an example bit stream and initial bit—buffer content [10010101101] containing seven symbols:
TABLE 3Bit—buffer1001010110100101011011010110101011010110110101Look ahead10001001011001Code Length1212212Symbol0−10+1+10+1
Although this simple concept is still applicable, actual JPEG Huffman decoding is more complex due to the special coding and code situations previously described. Algorithms for traditional AC-coefficient Huffman table creation and use are now presented.
In essence, the algorithms work as follows. The lookup table contains an entry for each possible eight-bit binary value that could be read from the bit stream. For an exemplary VLC code, e.g. 0100 for symbol s, all the elements of the table corresponding to indices 0100xxxx will map to symbol s and length 4, where “x” denotes either a 0 or 1 bit. To make the table creation fast, it is traditional to use the following algorithm.
Assume that the symbol lookup uses a constant HUFF—LOOKAHEAD number of bits. look—sym is a table that gives the symbol contained in the lookup bits; look—nbits is a table that tells how many bits are used by the symbol. If a particular look—nbits entry is not positive, the corresponding symbol is of a length more than HUFF—LOOKAHEAD bits. Huffcode[x] denotes the Huffinan code for a left-justified bit sequence denoted in binary by x. bits[x] denotes the number of codes with length x. Huffval[x] denotes the symbol associated with the binary code. The bottom four bits of this symbol denote the run and the top four bits denote a parameter from which the level can be derived. This particular meaning is for AC coefficients, and a different meaning applies to DC symbols. Note that the Huffval array contains the symbols, arranged in ascending order of the corresponding VLC code. Look—nbits is initialized to zero at the beginning. “<<” denotes Left shift operation. The lookup table creation is as follows.
p = 0;for (l = 1; l <= HUFF—LOOKAHEAD; l = l+1){for (i = 1; i <= bits[l]; i = i+1, p = p+1){lookbits = huffcode[p] << (HUFF—LOOKAHEAD − 1);for (ctr = 1 << (HUFF—LOOKAHEAD − 1); ctr > 0; ctr = ctr−1){look—nbits[lookbits] = l;look—sym[lookbits] = huffval[p];lookbits = lookbits + 1;}}}
With a lookup table set up by this algorithm, JPEG AC coefficient decoding can be illustrated by the following algorithm. Note that tree parsing must be used for the cases where the table lookup cannot produce a symbol. The tree parsing portion of the code is not relevant to this disclosure, but is understood by those skilled in the art and is therefore omitted.
for(k = 1; k < 64; k = k+1){Ensure there are at least HUFF—LOOKAHEAD bits in the bit—buffer;index = first HUFF—LOOKAHEAD bits in bit—buffer;x = look—nbits[index];if (x <= 0) {do tree parsing; then continue the loop.};s = look—sym[index];Remove x bits from bit—buffer;/* Get top 4 bits in r, bottom 4 bits in s */if(s > 0){k = k + r;Ensure there are at least s bits in the bit—buffer;Get the next s bits from bit—buffer, place in r;
One of ordinary skill in the art will recognize that the concepts taught herein can be tailored to a particular application in many other advantageous ways. In particular, those skilled in the art will recognize that the illustrated embodiments are selected from many alternative implementations that will become apparent upon reading this disclosure. Although specific JPEG and MPEG examples have been presented, the concepts described herein are applicable to other variable-length coding schemes and data sets. Such minor modifications are encompassed within the embodiments of the invention, and are intended to fall within the scope of the claims.
The preceding embodiments are exemplary. Although the specification may refer to “an”, “one”, “another”, or “some” embodiment(s) in several locations, this does not necessarily mean that each such reference is to the same embodiment(s), or that the feature only applies to a single embodiment.
s = HUFF—EXTEND(r, s);block[k]=s;}else{if(r != 15){/* We have reached End of block; exit the module. */}else{/* This is an escape sequence for run of 15; hence k = k + 15; */}}}
In this algorithm, the function y=HUFF—EXTEND(r, s) is defined as follows:
if ( r < (1<<(s − 1)){y = r + ((−1)<<s) + 1;}else{y = r;}
Further details are also available in the JPEG standard.